# python 编写排序代码 -20230215-

# 堆排序 -不稳定
def downAdjust(seq, lens, parents=0):
    """
    heapSort的配套子函数,向下调整(PS:向下调整的必须满足大根堆/小根堆)
    参数: 序列-可迭代对象 + 双亲位置索引
    升序采用的是大根堆进行排
    """
    child = parents * 2 + 1  # 计算的是左孩子
    while child < lens:
        if child + 1 < lens and (seq[child] < seq[child + 1]):
            child += 1
        if seq[child] > seq[parents]:
            seq[child], seq[parents] = seq[parents], seq[child]  # 作用是交换两者之间的值哦
            parents = child
            child = parents * 2 + 1
        else:
            break
    return


def heapSort(seq):
    lens = len(seq)
    # 首先将整个序列变成大根堆
    for n in range(lens - 1, -1, -1):  # 0, lens-1
        downAdjust(seq, lens, n)
    # 然后首位交换,进行选择调整堆
    for n in range(lens - 1):
        seq[0], seq[lens - 1 - n] = seq[lens - 1 - n], seq[0]
        downAdjust(seq, lens - n - 1)


# 交换排序 -冒泡排序-稳定
def bubblingSort(seq):
    lens = len(seq)
    for i in range(lens - 1):
        flag = True
        for j in range(lens - i - 1):
            if seq[j + 1] < seq[j]:
                seq[j + 1], seq[j] = seq[j], seq[j + 1]
                flag = False
        if flag:  # 优化，如果一轮中不存在交换，那么说明此时序列有序喔~
            break


# 插入排序 -希尔排序-不稳定
def shellSort(seq):
    lens = len(seq)
    group = lens
    while group > 1:
        group = group // 3 + 1
        i = 1
        while i <= lens - group:
            exc = i
            tmp = seq[exc]
            while exc > 0 and tmp < seq[exc - 1]:
                seq[exc] = seq[exc - 1]
                exc -= 1
            seq[exc] = tmp
            i += group


def mySort(seq):
    # heapSort(seq)  # 堆排序
    # bubblingSort(seq)  # 冒泡排序
    shellSort(seq)  # 希尔排序
    return


def testMain():
    arr1 = [1, 3, 0, 2, 4]
    arr2 = [1, 1, -2, 3, 4, 0]
    arr3 = [1, 2, 3, 4, 5, 6]
    arr4 = [5, 4, 3, 2, 1]
    mySort(arr1)
    mySort(arr2)
    mySort(arr3)
    mySort(arr4)
    for num in arr1:
        print(num, end=' ')
    print()
    for num in arr2:
        print(num, end=' ')
    print()
    for num in arr3:
        print(num, end=' ')
    print()
    for num in arr4:
        print(num, end=' ')
    print()


testMain()
